#light

open System

print_endline "Non-Memoized Fib\n----------------------"
let rec fib n =
    if n <= 2 then 1
    else fib(n-1) + fib(n-2)

let startTime = DateTime.Now
printfn "fib 35 = %d" (fib 35)
let endTime = DateTime.Now
printfn "%A" (endTime - startTime)


print_endline "\nMemoized Fib\n----------------------"
let fibM n =
    let t = new System.Collections.Generic.Dictionary<int,int>()
    let rec fibM' n =
        if t.ContainsKey(n) then t.[n]
        else if n <= 2 then 1
        else 
            let res = fibM'(n-1) + fibM'(n-2)
            t.Add(n,res)
            res
    fun n -> fibM' n

let startTimeM = DateTime.Now
let fibMemoized = fibM ()
printfn "fibMemoized 35 = %d" (fibMemoized 35)
let endTimeM = DateTime.Now
printfn "%A" (endTimeM - startTimeM)